package com.origin.niuke.point;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 接雨水
 * 给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个柱子高度图，计算按此排列的柱子，
 * 雨之后能接多少雨水。(数组以外的区域高度视为0)
 * 算法：单调栈、前后缀、双指针
 * 根据短板原理，能接多少水是由短板决定的
 *
 * @author yzh
 * @version 1.0
 * @date 2022/5/12 18:40
 */
public class NC128 {

    public long maxWater_monotoneStack(int[] arr) {
        long ans = 0;
        // 单调栈中的元素是单调递减的, 这样就可以找到比柱子大的最近的柱子
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < arr.length; i++) {
            // 由于每个元素只进行一次出栈和入栈，所以这里的时间复杂度为 O(1)
            while (!stack.isEmpty() && arr[i] > arr[stack.peek()]) {
                int cur = stack.pop();
                if (stack.isEmpty()) break;
                int l = stack.peek();
                int height = Math.min(arr[i], arr[l]) - arr[cur];
                ans += (i - l - 1) * height;
            }
            stack.push(i);
        }
        return ans;
    }

    /**
     * 算法: 前后缀
     * 时间复杂度: O(n)
     * 空间复杂度: O(n)
     * 当前柱子可以接雨水的量取决于柱子左边的最大值和右边的最大值, 从这两个最大值中取最小的
     */
    public long maxWater_prefixNum(int[] arr) {
        int n = arr.length;
        int[] pre_max = new int[n], suf_max = new int[n];
        pre_max[0] = arr[0];
        suf_max[n - 1] = arr[n - 1];
        for (int i = 1; i < n; i++) pre_max[i] = Math.max(pre_max[i - 1], arr[i]);
        for (int i = n - 2; i >= 0; i--) suf_max[i] = Math.max(suf_max[i + 1], arr[i]);
        long ans = 0;
        for (int i = 1; i < n - 1; i++) ans += Math.min(pre_max[i], suf_max[i]) - arr[i];
        return ans;
    }

    // 根据短板原理，能接多少水是由短板决定的

    /**
     * 双指针
     * 定义两个指针 f, t, 指向数组的头尾. 如果 arr[f] < arr[t], 那么左边的柱子的高度就确定了, 一定取最小的。
     * 反之, 右边的柱子的高度就确定了
     */
    public long maxWater_doublePointer(int[] arr) {
        if (arr == null || arr.length == 0) return 0;
        int n = arr.length, pre = 0, suf = n - 1, leftMax = 0, rightMax = 0;
        long ans = 0;
        while (pre < suf) {
            leftMax = Math.max(leftMax, arr[pre]);
            rightMax = Math.max(rightMax, arr[suf]);
            if (leftMax < rightMax) {
                ans += leftMax - arr[pre];
                ++pre;
            } else {
                ans += rightMax - arr[suf];
                --suf;
            }
        }
        return ans;
    }

}
